import java.util.ArrayList;
import java.util.List;

// 链表聚集交换
public class ListExchange {
    public static int solution(int length, List<Integer> linkedList, int k) {
        List<Integer> kPositions = new ArrayList<>();

        // 记录所有值为k的节点的位置
        for (int i = 0; i < length; i++) {
            if (linkedList.get(i) == k) {
                kPositions.add(i);
            }
        }

        int kCount = kPositions.size();
        if (kCount <= 1) {
            return 0;  // 如果k的数量为0或1，不需要交换
        }

        int minSwaps = Integer.MAX_VALUE;

        // 尝试所有可能的连续区间
        for (int start = 0; start < length - kCount + 1; start++) {
            int end = start + kCount - 1;
            int swaps = 0;

            // 计算将所有k移动到这个区间所需的交换次数
            for (int i = 0; i < kCount; i++) {
                int currentPos = kPositions.get(i);
                int targetPos = start + i;

                if (currentPos < start || currentPos > end) {
                    swaps++;
                }
            }

            minSwaps = Math.min(minSwaps, swaps);
        }

        return minSwaps;
    }

    public static void main(String[] args) {
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        list1.add(2);
        list1.add(1);
        list1.add(2);
        list1.add(1);
        List<Integer> list2 = new ArrayList<>();
        list2.add(0);
        list2.add(0);
        list2.add(1);
        list2.add(0);
        list2.add(0);
        List<Integer> list3 = new ArrayList<>();
        list3.add(6);
        list3.add(1);
        list3.add(6);
        list3.add(3);
        list3.add(6);
        list3.add(10);
        list3.add(40);
        list3.add(6);
        list3.add(6);
        list3.add(12);
        list3.add(6);
        System.out.println(solution(5, list1, 2) == 1);
        System.out.println(solution(5, list2, 1) == 0);
        System.out.println(solution(11, list3, 6) == 3);
    }
}